package array;

import java.util.Arrays;

public class MergeSortedArray {
    // [1,5,6,2,4,10,11]

    /**
     * 递归将数组两个区间有序元素合并
     *
     * @param a     原数组
     * @param p1    第一个区间指针
     * @param p1end 区间末尾指针
     * @param p2    第二个区间指针
     * @param p2end 区间末尾指针
     * @param b     第二个数组
     * @param k     数组用到的指针
     */
    public void merge(int[] a, int p1, int p1end, int p2, int p2end, int[] b, int k) {
        if (p1 > p1end) {
            for (int i = p2; i <= p2end; i++) {
                b[k] = a[i];
                k++;
            }
            return;
        }
        if (p2 > p2end) {
            for (int i = p1; i <= p1end; i++) {
                b[k] = a[i];
                k++;
            }
        }
        if (a[p1] < a[p2]) {
            b[k] = a[p1];
            merge(a, p1 + 1, p1end, p2, p2end, b, k + 1);
        } else {
            b[k] = a[p2];
            merge(a, p1, p1end, p2 + 1, p2end, b, k + 1);
            ;
        }
    }

    /**
     * 双指针合并数组两个区间元素
     * @param a 原数组
     * @param p1 第一个指针
     * @param p1end 第一个指针末尾
     * @param p2 第二个区间指针
     * @param p2end 第二个末尾
     * @param b 新数组
     */
    public void merge2(int[] a, int p1, int p1end, int p2, int p2end, int[] b) {
        int k = 0; // 新数组指针
        while (p1 <= p1end && p2 <= p2end) {
            if (a[p1] < a[p2]) {
                b[k] = a[p1];
                p1++;
            } else {
                b[k] = a[p2];
                p2++;
            }
            k++;
        }
        if (p1 > p1end) {
            for (int i = p2; i <= p2end; i++) {
                b[k] = a[i];
                k++;
            }
        }
        if (p2 > p2end) {
            for (int i = p1; i <= p1end; i++) {
                b[k] = a[i];
                k++;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 5, 6, 2, 4, 10, 11};
        int[] b = new int[array.length];
        MergeSortedArray m = new MergeSortedArray();
        m.merge2(array, 0, 2, 3, array.length - 1, b);
        System.out.println(Arrays.toString(b));
    }
}
